//
// Created by LiuYou on 2021/11/30.
//

#include <iostream>
#include <vector>
#include <iterator>


static void merge(std::vector<int>& arr, int l, int mid, int r) {
    // 准备的辅助空间, 这个辅助空间的大小由 l ~ r 位置有多少个元素。
    std::vector<int> help( r - l + 1 );
    std::cout << help.size() << std::endl;
    // 变量 index 是专门用来给 help 数组使用的。
    // 表示现在要在 index 位置上填充元素。
    int index = 0;
    // p1 指向的是左侧部分(l ~ mid)的下标, p1 一开始指向的是 l 位置。
    int p1 = l;
    // p2 指向右侧部分(mid + 1 ~ r)的下标, p2 一开始指向的是 mid + 1 位置。
    int p2 = mid + 1;

    // 然后接下来, 合并这两个有序数组。
    // 如果 p1 没有超过 mid(中点), 并且 p2 没有超过 r(终点)。那就是都没有越界。
    // p1 是左侧有序数组的下标, p2 是右侧有序数组的下标, 这两个下标都不能超过两个数组最大的下标。
    // 当 p1 和 p2 都没有越界的时候: 谁小拷贝到 help 辅助数组中去。
    // todo 笔记: 注意: 这里的 3 个while循环, 使用 后缀 ++ 是因为在拷贝完后, 指针要向后移动。
    while (p1 <= mid && p2 <= r) {
        if (arr[p1] <= arr[p2]) {
            help[index++] = arr[p1++];
        } else {
            help[index++] = arr[p2++];
        }
    }

    // 上面的这个while循环执行完后, 一定有一个数组会越界。所以有了下面这两个 while循环。
    // 这两个 while循环只会中一个(即执行一个)。

    // 如果 数组的左侧有序区间的数组下标没有越界(那就是 p2 的越界了。), 那么就把 p1 剩下的元素拷贝到 辅助数组中去。
    while (p1 <= mid) {
        help[index++] = arr[p1++];
    }
    // 如果 数组的右侧有序区间的数组下标没有越界(那就是 p1 的越界了。), 那么就把 p2 剩下的元素拷贝到 辅助数组中去。
    while (p2 <= r) {
        help[index++] = arr[p2++];
    }

    // 经过上面的 3 个while后, 辅助数组中就是两个有序数组 merge后的结果。
    // 然后将 help数组中的内容拷贝回原来的 arr数组 中去, 然后就完成了 l ~ r 位置上的 merge。
    for (int i = 0; i < help.size(); ++i) {
        arr[l + i] = help[i];
    }
}


/*
 * 让 arr数组 在 l 到 r 的范围上有序。
 */
static void sort(std::vector<int>& arr, int l, int r) {
    if (l == r) {
        return;
    } else {
        int mid = l + ((r - l) >> 1);
        sort( arr, l, mid );
        sort( arr, mid + 1, r );
        merge( arr, l, mid, r );
    }
}


static void mergeSort(std::vector<int>& arr) {
    if (arr.empty() || arr.size() == 1) {
        return;
    }

    sort( arr, 0, arr.size() - 1 );
}


int main(int argc, char** argv) {
    std::vector<int> arr{3, 1, 33, 23, 5, 14, 5, 1, 5, 111};
//    std::vector<int> arr{3, 4, 1, 2, 5};
    mergeSort( arr );
    std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, " " ));
    std::cout << std::endl;


    return 0;
}
